//题目:
// 给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
// 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>

using namespace std;
//代码:
class Solution 
{
public:
    struct compare
    {
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2)
        {
            return kv1.second>kv2.second || (kv1.second==kv2.second && kv1.first<kv2.first);
            //sort解释:先按pair<>内的第二个元素排降序,若second大小相同，则按first大小排序
            //priority_queue解释:先按second创建小根堆(升序)，若second相同，则按first创建大根堆(降序)
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        //法一:
        // map<string,int> CountMap;//key是单词，value是单词出现的次数
        // //将words中的所有单词记录在CountMap中
        // for(auto& str : words)
        // {
        //     CountMap[str]++;//插入时，已经按单词的字母顺序排好了
        // }
        // //先按CountMap.second的大小排序,若CountMap.second的大小相同，再按first排序

        // //sort(CountMap.begin(),CountMap.end());报错
        // //原因:sort()仅支持随机迭代器(自身能够++、--),而map是双向迭代器

        // //所以，需要将map内的数据放到一个随机迭代器中进行排序,这里选用vector
        // vector<pair<string,int>> vv(CountMap.begin(),CountMap.end());//迭代器区间初始化
        // //由于map内的数据有两个元素，所以这里用pair类型
        // //sort(vv.begin(),vv.end());报错
        // //原因:pair<first,second> 类型数据比较大小的规则是：若first小就小，否则看second小就小。与我们预期的不符

        // //故写一个仿函数，自己来定义排序的规则
        // sort(vv.begin(),vv.end(),compare());//compare()就是仿函数的使用

        // //取前k的元素
        // vector<string> ret;
        // for(int i=0;i<k;i++)
        // {
        //     ret.push_back(vv[i].first);
        // }
        // return ret;

        //法二:
        //1.创建一个哈希表
        unordered_map<string,int> hash;
        //2.统计单词出现的频次
        for(const auto& str:words)hash[str]++;
        //3.创建一个堆
        priority_queue<pair<string,int>,vector<pair<string,int>>,compare> heap;
        //4.为堆插入元素
        for(const auto& pir:hash)
        {
            heap.push(pir);
            if(heap.size()>k)heap.pop();
        }
        //5.提取结果
        vector<string> ret(k);
        for(int i=k-1;i>=0;i--)
        {
            ret[i]=heap.top().first;
            heap.pop();
        }
        return ret;
    }
};